#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/21 17:54
# ===========================================
#       题目名称： 21. 合并两个有序链表
#       题目地址： https://leetcode.cn/problems/merge-two-sorted-lists/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================
import math
from utils import StringUtils


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def mergeTwoLists(self, l1, l2):
        MAX_VALUE = (math.pow(2, 31) - 1) // 1
        res = None
        if not l1 and not l2:
            return res
        if not l1:
            return l2
        if not l2:
            return l1
        res = ListNode(MAX_VALUE)
        while l1 or l2:
            while l2 and (not l1 or l2.val < l1.val):
                if res.val is MAX_VALUE:
                    res.val = l2.val
                else:
                    temp_res = res
                    while temp_res.next:
                        temp_res = temp_res.next
                    temp_res.next = ListNode(l2.val)
                l2 = l2.next

            while l1 and (not l2 or l1.val <= l2.val):
                if res.val is MAX_VALUE:
                    res.val = l1.val
                else:
                    temp_res = res
                    while temp_res.next:
                        temp_res = temp_res.next
                    temp_res.next = ListNode(l1.val)
                l1 = l1.next
        return res

    def mergeTwoLists2(self, l1, l2):
        """
            实现有问题
        """
        MAX_VALUE = (math.pow(2, 31) - 1) // 1
        res = None
        if not l1 and not l2:
            return res
        if not l1:
            return l2
        if not l2:
            return l1
        res = ListNode(min(l1.val, l2.val), next=ListNode(max(l1.val, l2.val)))
        while l1 or l2:
            x, y = MAX_VALUE, MAX_VALUE
            if l1 and l1.next:
                l1 = l1.next
                x = l1.val
            if l2 and l2.next:
                l2 = l2.next
                y = l2.val
            if x == MAX_VALUE and y == MAX_VALUE:
                break
            elif x == MAX_VALUE or y == MAX_VALUE:
                temp_res = res
                while temp_res.next:
                    temp_res = temp_res.next
                cur_val = MAX_VALUE
                if x != MAX_VALUE:
                    cur_val = x
                if y != MAX_VALUE:
                    cur_val = y
                temp_val = temp_res.val
                temp_res.val = min(cur_val, temp_val)
                temp_res.next = ListNode(max(cur_val, temp_val))
            else:
                temp_res = res
                while temp_res.next:
                    temp_res = temp_res.next
                temp_val = temp_res.val
                arr = [temp_val, x, y]
                arr.sort()
                temp_res.val = arr[0]
                temp_res.next = ListNode(arr[1], ListNode(arr[2]))
        return res


if __name__ == '__main__':
    s = Solution()
    # [1,1,2,3,4,4]
    print(StringUtils.to_string(
        s.mergeTwoLists(l1=ListNode(1, ListNode(2, ListNode(4))), l2=ListNode(1, ListNode(3, ListNode(4))))
    ))
    # []
    print(StringUtils.to_string(s.mergeTwoLists(l1=None, l2=None)))
    # [0]
    print(StringUtils.to_string(s.mergeTwoLists(l1=None, l2=ListNode(0))))
    # [1,2,4,5]
    print(StringUtils.to_string(s.mergeTwoLists(l1=ListNode(5), l2=ListNode(1, ListNode(2, ListNode(4))))))
    # [-10,-10,-9,-7,-4,1,6,6]
    print(StringUtils.to_string(s.mergeTwoLists(l1=ListNode(-10, ListNode(-10, ListNode(-9, ListNode(-4, ListNode(1, ListNode(6, ListNode(6))))))), l2=ListNode(-7))))
    # [-9,-6,-3,-2,-1,1,5,6]
    print(StringUtils.to_string(s.mergeTwoLists(l1=ListNode(-2, ListNode(5)), l2=ListNode(-9, ListNode(-6, ListNode(-3, ListNode(-1, ListNode(1, ListNode(6)))))))))
